Parallel computing systems are known in which a plurality of individual processing elements, each including a microprocessor, associated memory and an input/output (I/O) device, are arranged in a binary tree configuration. One of the processing elements, referred to as the "root" processing element is connected to a host system and to two "child" processing elements. Each such child processing element in turn is a "parent" for two child processing elements connected thereto. The processing elements at the extremes of the tree are referred to as "leaf" processing elements, and have no additional children. Thus, in a binary tree computer, a large number of processing elements may be connected so that each processing element, except those at the root and the leaves of the tree, has a single parent and two (right and left) child processing elements.
U.S. Pat. Nos. 4,860,201 and 4,843,540 to Stolfo, that are assigned to the assignee of the present invention, describe such a system and are hereby incorporated by reference.
While the system described in the '201 and '540 patents represented a substantial step forward in the art, a number of problems remained. The system required the use of special parallel programming languages and could not be programmed using standard, commercially available languages. The system required specially trained programmers, who are not generally available, and the programs written could not be compiled using commercially available compilers. Additional significant limitations to such prior computer systems are that the processing elements spend a substantial portion their time dealing with communications up and down the tree, which reduces the processing throughput of the system, and that each processing element must be aware of its place in the tree, requiring software overhead. These difficulties have, until now, substantially limited the extent of application of binary tree computing systems.